Методы сортировки массива
Сортировка – это размещение данных в порядке возрастания или убывания. Сортировка массива осуществляется по значению его элементов. Существует множество способов сортировки. Рассмотрим три простых метода на примере сортировки целочисленных массивов данных по возрастанию.
Сортировка методом выбора. Алгоритм состоит в следующем. Среди элементов массива выбирается наименьший и меняется местами с первым. Далее рассматриваются элементы, начиная со второго, и наименьший из них меняется местами со вторым элементом. Так продолжается N-1 раз. При последнем проходе цикла при необходимости меняются местами предпоследний и последний элементы массива.
#include "iostream"
int main ()
{
const int N = 9;
int mas[N] = {420, 79, 429, 53, 908, 140, 897, 594, 682};
int i, j, indMin, temp;
for (i = 0; i < N-1; i++)
{
//принимаем за наименьший первый из рассматриваемых //элементов
indMin = i;
//поиск номера минимального элемента из неупорядоченных
for (j = i + 1; j < N; j++)
if (mas[j] < mas[indMin]) indMin = j;
//обмен элементов с номерами i и indMin
temp = mas[i];
mas[i] = mas[indMin];
mas[indMin] = temp;
}
return 0;
}
Пример сортировки методом выбора представлен в табл. 1.
Таблица 1.
Пример сортировки методом выбора
|
mas [0] |
mas [1] |
mas [2] |
mas [3] |
mas [4] |
mas [5] |
mas [6] |
mas [7] |
mas [8] |
indMin
|
Исходный массив |
|420 |
79 |
429 |
53 |
908 |
140 |
897 |
594 |
682 |
3 |
1-й проход цикла |
53 |
|79 |
429 |
420 |
908 |
140 |
897 |
594 |
682 |
1 |
2-й проход цикла |
53 |
79 |
|429 |
420 |
908 |
140 |
897 |
594 |
682 |
5 |
3-й проход цикла |
53 |
79 |
140 |
|420 |
908 |
429 |
897 |
594 |
682 |
3 |
4-й проход цикла |
53 |
79 |
140 |
420 |
|908 |
429 |
897 |
594 |
682 |
5 |
5-й проход цикла |
53 |
79 |
140 |
420 |
429 |
|908 |
897 |
594 |
682 |
7 |
6-й проход цикла |
53 |
79 |
140 |
420 |
429 |
594 |
|897 |
908 |
682 |
8 |
7-й проход цикла |
53 |
79 |
140 |
420 |
429 |
594 |
682 |
|908 |
897 |
8 |
8-й проход цикла |
53 |
79 |
140 |
420 |
429 |
594 |
682 |
897 |
|908 |
|
Сортировка методом «пузырька». Метод «пузырька» (или метод простого обмена) заключается в сравнении пары соседних элементов и замене их местами, если первый оказался больше второго. После этого сравнивается следующая пара и т.д. При выполнении этой последовательности действий элементы с большими значениями будут продвигаться (“всплывать” как пузырьки) в конец массива.
#include “iostream”
int main ()
{
const int N = 9;
int mas[N] = {420, 79, 429, 53, 908, 140, 897, 594, 682};
int bound, t, j, temp;
bound = N – 1;
do
{
t = 0;
for(j = 0; j <= bound – 1; j++)
if (mas[j] > mas[j + 1])
{
temp = mas[j];
mas[j] = mas[j + 1];
mas[j + 1] = temp;
t = j;
}
bound = t;
}
while (t);
return 0;
}
В начале сортировки ничего не известно о порядке размещения элементов. В переменной bound хранится индекс самого правого элемента массива, о котором не известно, занял ли он свою окончательную позицию или нет. В переменной t хранится индекс самого последнего элемента массива, который участвовал в обмене. Если после просмотра массива переменная t равна 0, то все элементы массива упорядочены и сортировка завершена. В противном случае, продолжаем просмотр массива, исключая элементы с индексом от t до N-1, которые уже заняли свои окончательные позиции. Пример выполнения сортировки методом пузырька для массива из 9 элементов, 420, 79, 429, 53, 908, 140, 897, 594, 682- приведен в табл. 2.
Таблица 2.
Пример выполнения сортировки методом «пузырька»
|
mas [0] |
mas [1] |
mas [2] |
mas [3] |
mas [4] |
mas [5] |
mas [6] |
mas [7] |
mas [8] |
bound |
Исходный массив |
420 |
79 |
429 |
53 |
908 |
140 |
897 |
594 |
682| |
8 |
1-й проход цикла |
79 |
420 |
53 |
429 |
140 |
897 |
594 |
682| |
908 |
7 |
2-й проход цикла |
79 |
53 |
420 |
140 |
429 |
594 |
682| |
897 |
908 |
6 |
3-й проход цикла |
53 |
79 |
140| |
420 |
429 |
594 |
682 |
897 |
908 |
2 |
4-й проход цикла |
|53 |
79 |
140| |
420 |
429 |
594 |
682 |
897 |
908 |
0 |
Как видно, после каждого прохода массива все элементы, расположенные правее самого последнего, который участвовал в обмене, и сам этот элемент занимают свои окончательные позиции (в табл. 2 эта часть массива отделена вертикальной чертой). При следующих просмотрах их проверять уже не нужно. Обратите внимание на то, что после третьего прохода еще четыре правых элемента, 420, 429, 594, 682- сразу заняли свои позиции, а при последнем проходе перемещений элементов вообще не было.
Сортировка методом простых вставок. Пусть существующие m из N элементов массива уже упорядочены, т.е.
mas*0+ ≤ mas*1+ ≤ … ≤ mas[m-1],
а элементы mas[m], mas[m+1+, …, mas[N-1+ не известны. Метод сортировки вставкой применяется в тех случаях, когда массив надо заполнить так, чтобы после вставки каждого нового элемента сохранилась его упорядоченность. Для этого осуществляется поиск подходящего для вставки места в уже заполненной части массива. Место для нового элемента освобождается путем сдвига больших элементов к концу массива.
#include "iostream"
int main ()
{
const int N = 9;
int mas[N] = {79, 420, 429};
int i, j, m, el;
m = 3;
//заполнение пустой части массива
for (i = m; i < N; i++)
{
//ввод нового элемента
cin >> el;
//поиск и высвобождение места под новый элемент
j = i - 1;
while (j >= 0 && el < mas[j])
{
//перемещение элемента mas[j] в позицию mas[j+1]
mas[j+1] = mas[j];
j--;
}
//вставка нового элемента в массив
mas[j+1] = el;
}
return 0;
}
Поиск ведется с конца заполненной части к началу массива следующим образом. Новый элемент el сравнивается по очереди с элементами mas[m-1], mas[m-2], mas[m-3+, … До тех пор, пока el меньше текущего элемента и не достигнуто начало массива, происходит высвобождение под него места путем перемещения большего элемента mas[j+ на одну позицию к концу массива. Новый элемент помещается в освободившуюся позицию. Пример заполнения массива с помощью алгоритма сортировки вставкой приведен в табл. 4. Здесь к уже существующим элементам, 79, 420, 429 (m=3) добавляются новые: 53, 908, 140, 897, 594, 682.
Таблица 3.
Пример сортировки простой вставкой
mas [0] |
mas [1] |
mas [2] |
mas [3] |
mas [4] |
mas [5] |
mas [6] |
mas [7] |
mas [8] |
79 |
420 |
429 |
:53 |
|
|
|
|
|
↑ 53 |
79 |
420 |
429 |
:908 |
|
|
|
|
53 |
79 |
420 |
429 |
↑ 908 |
:140 |
|
|
|
53 |
79 |
↑ 140 |
420 |
429 |
908 |
:897 |
|
|
53 |
79 |
140 |
420 |
429 |
↑ 897 |
908 |
:594 |
|
53 |
79 |
140 |
420 |
429 |
↑ 594 |
897 |
908 |
:682 |
53 |
79 |
140 |
420 |
429 |
594 |
↑ 682 |
897 |
908 |
Для заполнения пустого массива нужно прежде ввести первый элемент (m=1), а после выполнить действия алгоритма сортировки вставкой.
...
cin >> mas[0];
for (i = 1; i < N; i++)
{
cin >> el;
j = i - 1;
while (j >= 0 && el < mas[j])
{
mas[j+1] = mas[j];
j--;
}
mas[j+1] = el;
}
...
Поиск элемента по заданному значению. В данном алгоритме последовательно просматривается весь массив. Начинаем поиск с начала массива и продолжаем до конца, пока не будет найден искомый элемент; затем останавливаемся. Если элемент найден, то переменной ind присваиваем номер этого элемента.
#include "iostream"
int main()
{
const int N = 9;
int k, ind, i;
//задание значений элементов массива
int mas[N] = {420, 79, 429, 53, 908, 140, 897, 594, 682};
cout << "Введите значение для поиска: ";
cin >> k;
//поиск значения k в массиве
ind = -1;
for (i = 0; i < N; i++)
if (mas[i] == k)
{
ind = i;
break;
}
//вывод результата поиска
if (ind < 0)
cout << "Искомое значение в массиве не найдено!\n";
else
cout << "Искомый элемент mas[" << ind << "] = " << mas[ind] << "\n";
return 0;
}
Бинарный поиск. Если массив упорядочен, то можно использовать более эффективный алгоритм поиска, например, бинарный поиск (или метод деления пополам). Обозначим через l – левую границу поиска, r – правую границу поиска и sr – индекс элемента, находящегося в середине массива. Сравним искомый элемент k со средним элементом a[sr]. Если они совпадают, то поиск завершен успешно и местоположение определено. Если искомый элемент больше, то берем правую половину массива (элементы с индексами от sr + 1 до r); если меньше – то левую (элементы с индексами от l до sr – 1). Процесс повторяется до тех пор, пока не будет найден нужный элемент или диапазон поиска не будет исчерпан.
#include "iostream"
int main()
{
const int N = 9;
int k, l, r, sr, ind;
//задание значений элементов массива
int mas[N] = {53, 79, 140, 420, 429, 594, 682, 897, 908};
cout << "Введите значение для поиска: ";
cin >> k; //поиск значения k в массиве
ind = -1;
l = 0;
r = N - 1;
while ( l <= r)
{
sr = (l + r) / 2;
if (mas[sr] == k)
{
ind = sr;
break;
}
if (mas[sr] < k) l = sr + 1;
else r = sr - 1;
}
//вывод результата поиска
if (ind < 0)
cout << "Искомое значение в массиве не найдено!\n";
else cout << "Искомый элемент mas[" << ind << "] = " << mas[ind] << "\n";
return 0;
}